package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:2841. 几乎唯一子数组的最大和
 *
 * 给你一个整数数组 nums 和两个正整数 m 和 k 。
 * 请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
 * 如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
 * 子数组指的是一个数组中一段连续 非空 的元素序列。
 *
 * <p>
 * User:Mr.Du
 * Date:2024/4/13
 * Time:17:24
 */
public class MaxSum {

    public long maxSum(List<Integer> nums, int m, int k) {
        Map<Integer, Integer> mp = new HashMap<>();
        long res = 0, sum = 0;
        for(int i = 0;i < k;i++){
            mp.put(nums.get(i), mp.getOrDefault(nums.get(i), 0) + 1);
            sum += nums.get(i);
        }
        if(mp.size() >= m) res = sum;
        for(int i = k;i < nums.size();i++){
            sum += nums.get(i) - nums.get(i - k);
            mp.put(nums.get(i), mp.getOrDefault(nums.get(i), 0) + 1);
            if(mp.get(nums.get(i - k)) > 1) mp.put(nums.get(i - k), mp.get(nums.get(i - k)) - 1);
            else mp.remove(nums.get(i - k));
            if(mp.size() >= m) res = Math.max(res, sum);

        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 3};
        List<Integer> list = new ArrayList<>();
        for(int i : nums) list.add(i);

        System.out.println(new MaxSum().maxSum(list, 2, 2));
    }
}
